Open Reading Group — Papersᵞ

Wellcome to Open Reading Group's library,

You can find here all papers liked or uploaded by Open Reading Group
together with brief user bio and description of her/his academic activity.

### Upcoming readings: No upcoming readings for now... ### Past Readings: - 21/05/2018 [Graph Embedding Techniques, Applications, and Performance: A Survey](https://papers-gamma.link/paper/52) - 14/05/2018 [A Fast and Provable Method for Estimating Clique Counts Using Turán’s Theorem](https://papers-gamma.link/paper/24) - 07/05/2018 [VERSE: Versatile Graph Embeddings from Similarity Measures](https://papers-gamma.link/paper/48) - 30/04/2018 [Hierarchical Clustering Beyond the Worst-Case](https://papers-gamma.link/paper/45) - 16/04/2018 [Scalable Motif-aware Graph Clustering](https://papers-gamma.link/paper/18) - 02/04/2018 [Practical Algorithms for Linear Boolean-width](https://papers-gamma.link/paper/40) - 26/03/2018 [New Perspectives and Methods in Link Prediction](https://papers-gamma.link/paper/28/New%20Perspectives%20and%20Methods%20in%20Link%20Prediction) - 19/03/2018 [In-Core Computation of Geometric Centralities with HyperBall: A Hundred Billion Nodes and Beyond](https://papers-gamma.link/paper/37) - 12/03/2018 [Diversity is All You Need: Learning Skills without a Reward Function](https://papers-gamma.link/paper/36) - 05/03/2018 [When Hashes Met Wedges: A Distributed Algorithm for Finding High Similarity Vectors](https://papers-gamma.link/paper/23) - 26/02/2018 [Fast Approximation of Centrality](https://papers-gamma.link/paper/35/Fast%20Approximation%20of%20Centrality) - 19/02/2018 [Indexing Public-Private Graphs](https://papers-gamma.link/paper/19/Indexing%20Public-Private%20Graphs) - 12/02/2018 [On the uniform generation of random graphs with prescribed degree sequences](https://papers-gamma.link/paper/26/On%20the%20uniform%20generation%20of%20random%20graphs%20with%20prescribed%20d%20egree%20sequences) - 05/02/2018 [Linear Additive Markov Processes](https://papers-gamma.link/paper/21/Linear%20Additive%20Markov%20Processes) - 29/01/2018 [ESCAPE: Efficiently Counting All 5-Vertex Subgraphs](https://papers-gamma.link/paper/17/ESCAPE:%20Efficiently%20Counting%20All%205-Vertex%20Subgraphs) - 22/01/2018 [The k-peak Decomposition: Mapping the Global Structure of Graphs](https://papers-gamma.link/paper/16/The%20k-peak%20Decomposition:%20Mapping%20the%20Global%20Structure%20of%20Graphs)

☆

A Fast and Provable Method for Estimating Clique Counts Using Turán’s Theorem

Comments:

### Arboricity is different from degeneracy: - "A classic bound on the degeneracy asserts that $\alpha(G)\leq \sqrt{2m}$ (Lemma 1 of [12])." [12] is related to the arboricity! The degeneracy $\alpha$ is the maximum of the minimum degree of any subgraph. The arboricity $\beta$ is the minimum number of forests needed to cover all edges in the graph. In [12], $\beta\leq ceil(\sqrt{2m+n})/2$ is proven. We have, $\beta \leq \alpha \leq 2 \beta − 1$. - "By a theorem of Chiba-Nishizeki [12], we can argue that the number of vertices in any set of the Turan shadow is at most $\sqrt{2m}$ (where $m$ is the number of edges in G)." We can actually state that the number of vertices in any set of the Turan shadow is at most $\alpha$ where $\alpha$ is the degeneracy of the input graph (in large and sparse real-world graphs we generally have $\alpha<<\sqrt{2m}$). ### Tight bound on the shadow size: "Indeed, we can design instances where Claim 5.7 is tight (a set of $n/\alpha$ Erdos-Renyi graphs $G(\alpha,1/3))$." It is not clear why this is a tight bound. $\alpha$ is the degeneracy of the input graph (the graph "$n/\alpha$ Erdos-Renyi graphs $G(\alpha,1/3))$" may not have degeneracy $\alpha$). ### Scalability of an enumeration procedure: "The primary challenge is combinatorial explosion. An autonomous system network with ten million edges has more than a trillion 10-cliques. Any enumeration procedure is doomed to failure." The fact that there can be "a trillion 10-cliques" may not be enough to discard an enumeration procedure. For instance, the program (counting from 1 to one trillion) generated by the following C code terminates within few minutes on a commodity machine. ```c main() { unsigned long long i=0; while (i ＜ 1e12) { i++; } } ``` ### Minors: - "Denote the number of k-cliques by $C$, then the success probability is $C/{ n \choose k}$. Thus, we can estimate this probability using ${ n \choose k}/C$ samples." This may need some explanations. ### Typos: - "It will be convenient to express this result in terms on k-clique densities."

Stranger at 2018-05-10 16:51:28

Read the paper, add your comments…

Papersγ / Open Reading Group

Wellcome to Open Reading Group's library,

Comments:

Comments:

Comments:

Papers^γ / Open Reading Group